/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class UniquePath {

	/**
	Unique Path
	A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

	The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

	How many possible unique paths are there?
	 */
	public int uniquePaths(int m, int n) {
		if (m <= 0 && n <= 0)
			return 0;
		int[][] dp = new int[m + 1][n + 1];
		dp[m - 1][n] = 1;

		for (int x = m - 1; x >= 0; x--) {
			for (int y = n - 1; y >= 0; y--) {
				dp[x][y] = dp[x + 1][y] + dp[x][y + 1];
			}
		}

		return dp[0][0];
	}

	/**
	 Unique Path II
	Follow up for "Unique Paths":

	Now consider if some obstacles are added to the grids. How many unique paths would there be?

	An obstacle and empty space is marked as 1 and 0 respectively in the grid.

	For example,

	There is one obstacle in the middle of a 3x3 grid as illustrated below.

	[
	[0,0,0],
	[0,1,0],
	[0,0,0]
	]

	The total number of unique paths is 2.

	Note: m and n will be at most 100.
	 */
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		// Start typing your Java solution below
		// DO NOT write main() function

		if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0)
			return 0;

		int rows = obstacleGrid.length;
		int cols = obstacleGrid[0].length;
		int[][] dp = new int[rows + 1][cols + 1];
		dp[rows - 1][cols] = 1;

		for (int row = rows - 1; row >= 0; row--) {
			for (int col = cols - 1; col >= 0; col--) {
				if (obstacleGrid[row][col] == 1
						|| (dp[row + 1][col] == -1 && dp[row][col + 1] == -1))
					dp[row][col] = -1;
				else {
					if (dp[row + 1][col] != -1)
						dp[row][col] += dp[row + 1][col];
					if (dp[row][col + 1] != -1)
						dp[row][col] += dp[row][col + 1];
				}
			}
		}

		return dp[0][0] == -1 ? 0 : dp[0][0];
	}

	/**
	 * 
	 */
	public UniquePath() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
